//https://leetcode.cn/problems/linked-list-cycle-ii/
package codeRandomThoughts.Test142环形链表II;

import codeRandomThoughts.utils.ListNode;

import java.util.HashSet;

//二刷
public class Solution2 {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {//防止越界
            fast = fast.next.next;//fast每次走两步
            slow = slow.next;//slow每次走一步

            //如果二者相遇
            //此处参考笔记上推出的公式
            if (fast == slow) {
                ListNode meetPoint = slow;
                ListNode start = head;
                while (meetPoint != start) {
                    meetPoint = meetPoint.next;
                    start = start.next;
                }
                return start;
            }
        }
        return null;//没有环
    }

    //用哈希表也可以,但是没有这个巧妙
    public ListNode detectCycleHash(ListNode head) {
        ListNode pos = head;
        HashSet<ListNode> visited = new HashSet<>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}
